package day0804;

class ChaBingJi {
    class UnionFind{
        int[] root;
        int[] rank;
        int count;
        public UnionFind(char[][] grid){
            int row = grid.length;
            int col = grid[0].length;
            count = 0;
            root = new int[row*col];
            rank = new int[row*col];
            for(int i = 0;i < row;i++){//初始化
                for (int j = 0; j <col; j++) {
                    if(grid[i][j] == '1'){
                        root[i*col+j] = i*col+j;//更新值为1的元素  让其索引值=值
                        count++;
                    }
                    rank[i*col+j] =0;//初始化 高度为0
                }
            }

        }
        public int find(int x){
            if (root[x] != x){
                root[x] = find(root[x]);//递归查找根
            }
            return root[x];
        }
        public void union(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY){
                if(rank[rootX] >rank[rootY]){
                    root[rootY] = rootX;//值
                }else if(rank[rootX] <rank[rootY]){
                    root[rootX] = rootY;//值
                }else{
                    root[rootY] = rootX;//值
                    rank[rootX]+=1;
                }
                count--;
            }
        }
        public int getCount(){
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        if(grid == null || grid.length==0){
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        UnionFind unionFind = new UnionFind(grid);
        for (int i = 0; i <row; i++) {
            for (int j = 0; j <col; j++) {
                if(grid[i][j] =='1'){
                    // if(i-1>=0 && grid[i-1][j] == '1'){//左
                    //     unionFind.union(i*col+j,(i-1)*col+j);
                    // }
                    if(i+1<row && grid[i+1][j] == '1'){//右
                        unionFind.union(i*col+j,(i+1)*col+j);
                    }
                    // if(j-1>=0 && grid[i][j-1] == '1'){//上
                    //     unionFind.union(i*col+j,i*col+j-1);
                    // }
                    if(j+1<col && grid[i][j+1] == '1'){//下
                        unionFind.union(i*col+j,i*col+j+1);
                    }
                }
            }
        }
        return unionFind.getCount();
    }
}